package NC21_链表内指定区间反转;

import sun.security.x509.InvalidityDateExtension;

import java.util.*;

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Solution {
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 1. 走 m - 1 步到 m 的前一个节点
        for (int i = 0; i < m - 1; i++){
            pre = pre.next;
        }

        // 2. 走 n - m + 1 步到 n 节点
        ListNode rightNode = pre;
        for (int i = 0; i < n - m + 1; i++){
            rightNode = rightNode.next;
        }

        // 3. 截取出一个子链表
        ListNode leftNode = pre.next;
        ListNode cur = rightNode.next;

        // 4. 切断连接
        pre.next = null;
        rightNode.next = null;

        // 5. 反转链表
        reverse(leftNode);

        // 6. 接回原来的链表
        pre.next = rightNode;
        leftNode.next = cur;
        return dummyNode.next;
    }

    private void reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            //Cur_next 指向cur节点的下一个节点
            ListNode Cur_next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = Cur_next ;
        }
    }

}